/*
 * @lc app=leetcode.cn id=316 lang=typescript
 *
 * [316] 去除重复字母
 */

// @lc code=start
function removeDuplicateLetters(s: string): string {
  // 统计每个字符出现的次数
  const hash: Map<string, number> = new Map();
  for (const c of s) {
    hash.set(c, (hash.get(c) ?? 0) + 1);
  }

  // 单调递增栈，保证字符是按照相对升序
  const stack = [];
  for (const c of s) {
    // 栈中没有当前字符才可以入栈
    if (!stack.includes(c)) {
      while (stack.length && hash.get(stack[stack.length - 1]) && c < stack[stack.length - 1]) {
        stack.pop();
      }
      stack.push(c);
    }
    hash.set(c, hash.get(c) - 1);
  }

  return stack.join('');
}
// @lc code=end
